package 二叉树相关问题.经典二叉树问题;


public class 从前序遍历和中序遍历构造二叉树 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
          return buildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }

    private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {

        if (preStart>preEnd || inStart>inEnd)
            return null;
        int rootVal=preorder[preStart];
        int index=0;
        //找到根节点在中序遍历中的位置
        for (int i = inStart; i <=inEnd ; i++) {
            if (inorder[i]==rootVal){
                index=i;
                break;
            }
        }
        int leftLength=index-inStart;
        TreeNode root=new TreeNode(rootVal);
        root.left=buildTree(preorder,preStart+1,preStart+leftLength,inorder,inStart,index-1);
        root.right=buildTree(preorder,preStart+leftLength+1,preEnd,inorder,index+1,inEnd);
        return root;
    }
}
